package com.foxzzz.greedy;


import java.util.Arrays;

public class Solution455 {
    //n*n+m*m+m
    public int findContentChildren1(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int cookie = 0;
        int child = 0;
        while (child < g.length && cookie < s.length) {
            if (g[child] <= s[cookie]) {
                child++;
            }
            cookie++;
        }
        return child;
    }

    public int findContentChildren(int[] g, int[] s) {
        int num = 0;
        for (int i = 0; i < g.length; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;
            for (int j = 0; j < s.length; j++) {
                if (s[j] != -1 && s[j] >= g[i]) {
                    if (min > s[j] - g[i]) {
                        min = s[j] - g[i];
                        index = j;
                        if (min == 0) {
                            break;
                        }
                    }
                }
            }
            if (index != -1) {
                s[index] = -1;
                num++;
            }
        }
        return num;
    }

    public static void main(String[] args) {
        System.out.println(new Solution455().findContentChildren(new int[]{1, 2, 3}, new int[]{1, 1}));
        System.out.println(new Solution455().findContentChildren(new int[]{1, 2}, new int[]{1, 2, 3}));
    }
}
